第5章 · 第二部分

优化模型中逻辑变量的妙用

用0-1变量表达逻辑关系、处理非凸约束、构建复杂模型

⚡ 核心问题

0-1变量在优化建模中最核心的价值是什么？

✅ 正确！0-1变量（逻辑变量）是建模的"万能钥匙"：它可以表达条件约束、择一约束、分段函数、指示关系等，将复杂的非凸、逻辑条件转化为混合整数线性规划（MILP）。

❌ 0-1变量的能力远超"是与否"的二元选择。它能系统性地将逻辑推理转化为代数约束，是连接离散逻辑与连续优化的桥梁。

🎯 学习目标

掌握用0-1变量表达基本逻辑关系（与/或/非/蕴含/异或）的代数方法
理解指示约束（indicator constraints）的建模与大M方法
能够将分段线性函数转化为MIP形式
掌握"择一约束"（either-or / disjunctive constraints）的建模
理解TSP模型中子环消除约束的建模逻辑
能独立完成含逻辑条件的投资组合/设施选址等应用建模

1 0-1 变量：从逻辑到代数的翻译

0-1变量不仅是"选或不选"的标志，更是将逻辑命题转化为线性约束的核心工具。设 $x_i \in \B$ 为0-1变量：

逻辑关系	语义	线性约束表示
$P \land Q$（与）	$x_P=1$ 且 $x_Q=1$	$x_P=1,\; x_Q=1$
$P \lor Q$（或）	$x_P=1$ 或 $x_Q=1$（可同时）	$x_P + x_Q \ge 1$
$\neg P$（非）	$x_P=0$	$x_P=0$ 或用 $1-x_P$
$P \oplus Q$（异或）	恰好一个为1	$x_P + x_Q = 1$
$P \Rightarrow Q$（蕴含）	若 $x_P=1$ 则 $x_Q=1$	$x_P \le x_Q$
$P \lor Q \Rightarrow R$	若P或Q，则必须R	$x_P \le x_R,\; x_Q \le x_R$
至少k个为真	$\sum x_i \ge k$	$\sum_{i} x_i \ge k$
至多k个为真	$\sum x_i \le k$	$\sum_{i} x_i \le k$
恰好k个为真	$\sum x_i = k$	$\sum_{i} x_i = k$
两者都选或都不选	$x_2=x_6$	$x_2 - x_6 = 0$

🔑 记忆诀窍

蕴含 $P \Rightarrow Q$ → $x_P \le x_Q$：如果P选（1），则Q必须选（1），所以$1 \le 1$；如果P不选（0），Q随意（$0 \le$ 任意）。

互斥 $P$ 与 $Q$ 不能同时选 → $x_P + x_Q \le 1$

2 指示约束（Indicator Constraints）

指示约束刻画："如果某个条件成立，则某个线性约束才需要被满足"。

典型形式

用0-1变量 $\delta$ 指示命题 $P$ 是否为真：

$$\delta = 1 \;\Longleftrightarrow\; a^T x \le b$$

关键应用：指示变量 $\delta$ 与连续条件 $x>0$ 的双向关系——

$$\begin{aligned} x &> 0 \;\Longrightarrow\; \delta = 1 \quad &\Rightarrow\quad & x \le M\delta \\ \delta = 1 &\;\Longrightarrow\; x \ge m \quad &\Rightarrow\quad & x \ge m\delta \end{aligned}$$

其中 $M$ 是 $x$ 的充分大上界，$m$ 是 $x$ 取正时的充分小下界。

⚠️ Big-M 方法的陷阱

$M$ 值的选择至关重要：

$M$ 太小 → 可能切掉可行解（不可行）
$M$ 太大 → LP松弛太弱，求解效率急剧下降
最佳实践：从问题语义出发，取理论上最紧的上界

3 分段线性函数的线性化

许多实际问题涉及分段成本（如阶梯电价、批量折扣），模型如下：

对分段线性函数 $f(x)$，取断点 $(a_k, b_k)$，引入权重 $\lambda_k$：

$$\begin{aligned} x &= \sum_k \lambda_k a_k \\ f(x) &= \sum_k \lambda_k b_k \\ \sum_k \lambda_k &= 1,\quad \lambda_k \ge 0 \end{aligned}$$

SOS2（Special Ordered Set of type 2）约束：$\{\lambda_k\}$ 中至多两个相邻的取正值。

对 $n$ 段的分段函数，引入 $n$ 个0-1变量 $z_k$：

$$\begin{aligned} a_k z_k \le x_k &\le a_{k+1} z_k \\ \sum_k z_k &= 1,\quad z_k \in \B \end{aligned}$$

每段内 $x$ 在该段内线性插值。SOS2更紧但需要求解器支持；0-1方法通用但变量更多。

4 择一约束（Either-Or / Disjunctive Constraints）

要求满足两组约束中的至少一组：

$$\begin{aligned} &\text{要么 } a_1^T x \le b_1 \\ &\text{要么 } a_2^T x \le b_2 \end{aligned}$$

引入0-1变量 $y \in \B$ 和充分大的 $M$：

$$\begin{aligned} a_1^T x &\le b_1 + M(1-y) \\ a_2^T x &\le b_2 + My \end{aligned}$$

当 $y=1$：第一个约束生效，第二个被"关掉"（$+M$ 使右边极大）；当 $y=0$：反之。

推广：离散值约束

变量 $x$ 只能取离散集合 $\{v_1, v_2, \dots, v_k\}$：

$$x = \sum_{j=1}^{k} v_j \delta_j,\quad \sum_{j=1}^{k} \delta_j = 1,\quad \delta_j \in \B$$

5 双线性项的0-1线性化

当涉及0-1变量与连续变量的乘积 $x \cdot \delta$（$\delta \in \B$），可直接线性化：

令 $w = x \cdot \delta$，则引入线性约束： $$\begin{aligned} w &\le M\delta \\ w &\ge m\delta \\ w &\le x - m(1-\delta) \\ w &\ge x - M(1-\delta) \end{aligned}$$

当 $\delta=0$：$w=0$；当 $\delta=1$：$w=x$。$M$ 和 $m$ 分别是 $x$ 的上下界。

对比第5.1章的 McCormick 方法

McCormick 方法适用于两个连续变量的乘积（松弛近似）；这里的方法适用于0-1 × 连续的乘积（精确等价转化）。在实际建模中，如果能把双线性问题重构为含0-1变量的形式，就能得到精确的MIP模型。

6 应用案例：投资组合选择

问题描述

预算 $14,000。6个投资项目，各需投资 $c_j$，净现值 $v_j$。需满足以下逻辑约束：

$$\begin{aligned} \max \;& 16x_1 + 22x_2 + 12x_3 + 8x_4 + 11x_5 + 19x_6 \\ \text{s.t.} \;& 5x_1 + 7x_2 + 4x_3 + 3x_4 + 4x_5 + 6x_6 \le 14 \\ & x_j \in \B, \; j = 1,\dots,6 \end{aligned}$$

这是一个0-1背包问题（0-1 Knapsack Problem）。

#	逻辑条件	线性约束
1	恰好选3支股票	$x_1+x_2+x_3+x_4+x_5+x_6 = 3$
2	若选2，则必须选1	$x_2 \le x_1$
3	若选1，则不选3	$x_1 + x_3 \le 1$
4	4和5中恰好选一个	$x_4 + x_5 = 1$
5	2和6要么都选，要么都不选	$x_2 - x_6 = 0$

拖动预算滑块，观察最优解的变化：

预算（千元）：14

调整预算观察不同约束下的最优投资组合...

7 TSP 模型：子环消除的逻辑挑战

旅行商问题（TSP）是展示逻辑变量建模能力的最佳案例之一。

基础赋值模型

设 $x_{ij} \in \B$ 表示是否从城市 $i$ 到城市 $j$。

$$\begin{aligned} \min \;& \sum_{i,j} c_{ij} x_{ij} \\ \text{s.t.} \;& \sum_{j} x_{ij} = 1 \quad \forall i \quad &\text{(每个城市离开一次)}\\ & \sum_{i} x_{ij} = 1 \quad \forall j \quad &\text{(每个城市到达一次)} \end{aligned}$$

但这还不够！以上约束无法消除子环（subtours）。

MTZ 子环消除约束（Miller-Tucker-Zemlin）

引入连续变量 $u_i$（访问顺序），加入：

$$u_i - u_j + n \cdot x_{ij} \le n-1,\quad \forall i,j \ge 2,\; i \ne j$$ $$1 \le u_i \le n-1$$

原理：如果 $x_{ij}=1$（从 $i$ 到 $j$），则 $u_j \ge u_i + 1$，迫使访问顺序严格递增，从而阻断子环。

🖱️ 交互式 TSP 演示

点击画布添加城市，点击"求解"查看结果。

8 逻辑变量建模总览

场景	核心技巧	关键公式
逻辑关系	0-1变量的线性不等式	$x_2 \le x_1$（蕴含）
指示约束	Big-M 方法	$x \le M\delta,\; x \ge m\delta$
分段函数	SOS2 或 0-1分段	$\sum \lambda_k a_k,\; \sum z_k=1$
择一约束	互补Big-M	$a_1^T x \le b_1 + M(1-y)$
双线性(0-1×连续)	四约束精确线性化	$w \le M\delta,\; w \ge m\delta,\dots$
子环消除(TSP)	MTZ 顺序变量	$u_i-u_j+n x_{ij} \le n-1$
固定费用	0-1 + Big-M	$\text{cost} = Fy + cx,\; x \le My$

📚 延伸阅读

推荐阅读微信文章："优化模型的建立与转化"和"优化中逻辑约束建模与Gurobi实现——线性化技巧小结"，涵盖更多高级线性化技巧和求解器实现细节。

📝 章节检测（共3题）

每题选择后查看详细解析。

1 逻辑关系的线性化

逻辑命题"如果选项目A，则不能选项目B"的正确线性约束是：

2 Big-M 方法中 M 值的选择

在 Big-M 方法中，$M$ 值的选择对求解效率有重要影响。以下说法正确的是：

3 TSP 子环消除

TSP的赋值模型（assignment model）为什么不能保证得到一条完整回路？